package query.subgraph;

import java.io.IOException;
import java.util.ArrayList;

import model.AdjacencyList;
import model.Edge;
import model.Graph;
import model.Node;
import model.QueryAdjacencyList;
import model.QueryEdge;
import model.QueryGraph;
import model.QueryManager;

public class SubGraphQueryManager extends QueryManager {

	private Graph dataGraph;

	private QueryGraph queryGraph;

	private int[] rlt;

	private ArrayList<Graph> rlts = new ArrayList<Graph>();

	private Graph rltG = new Graph();

	public static void main(String args[]) {
		SubGraphQueryManager qManager = new SubGraphQueryManager();
		Graph g = null;
		QueryGraph q1 = null, q2 = null, q3 = null;
		try {
			g = Graph.loadFromTextFile("dataset/data graph/node.txt",
					"dataset/data graph/edge.txt",
					"dataset/data graph/nodeSchema.txt",
					"dataset/data graph/edgeSchema.txt");
			q1 = QueryGraph.loadFromTextFile(
					"dataset/query graph/4nodes/queryNode.txt",
					"dataset/query graph/4nodes/queryEdge.txt");
			q2 = QueryGraph.loadFromTextFile(
					"dataset/query graph/4nodes with labels/queryNode.txt",
					"dataset/query graph/4nodes with labels/queryEdge.txt");
			q3 = QueryGraph
					.loadFromTextFile(
							"dataset/query graph/4nodes with labels and attributes/queryNode.txt",
							"dataset/query graph/4nodes with labels and attributes/queryEdge.txt");
			System.out.println(g.edges.size());
			System.out.println(q1.edges.size());
			System.out.println(q2.edges.size());
			System.out.println(q3.edges.size());
		} catch (IOException e) {
			// TODO Auto-generated catch block
			System.err.println("INPUT ERROR");
			e.printStackTrace();
		}
		qManager.subgraphQuery(g, q3);
	}

	@Override
	public ArrayList<Graph> subgraphQuery(Graph dataGraph, QueryGraph queryGraph) {
		// TODO Auto-generated method stub
		this.dataGraph = dataGraph;
		this.queryGraph = queryGraph;
		rlt = new int[queryGraph.nodes.size()];
		return this.subgraphQuery();
	}

	public ArrayList<Graph> subgraphQuery() {
		queryGraph.initializeAdjacencyList();
		dataGraph.initializeAdjacencyList();
		queryGraph.initializeSearchSpace(dataGraph);
		this.refineSearchSpace();
		for (int k = 0; k < queryGraph.searchSpace.size(); k++) {
			System.out.println(queryGraph.searchSpace.get(k).size());
		}
		this.DFSSearch(0);
		return rlts;
	}

	public void DFSSearch(int index) {
		for (int counter = 0; counter < queryGraph.searchSpace.get(index)
				.size(); counter++) {
			int nodeId = queryGraph.searchSpace.get(index).get(counter);
			if (isIn(nodeId)) {
				continue;
			}
			rltG.addNode(dataGraph.nodes.get(nodeId));
			if (!check(index, nodeId)) {
				continue;
			} else {
				if (index < queryGraph.nodes.size() - 1) {
					DFSSearch(index + 1);
				} else {
					System.out.println("in");
					rlts.add(new Graph(rltG));
					for (int i = 0; i < rltG.nodes.size(); i++) {
						System.out.print(rltG.nodes.get(i).getId() + " ");
					}
					System.out.println("");
					Node node = rltG.nodes.remove(rltG.nodes.size() - 1);
					rltG.removeEdges(node);
				}
			}
		}
		if (rltG.nodes.size() > 0) {
			Node node = rltG.nodes.remove(rltG.nodes.size() - 1);
			rltG.removeEdges(node);
		}
	}

	// refine the search space to accelerate seaching process
	private void refineSearchSpace() {
		for (int i = 0; i < queryGraph.searchSpace.size(); i++) {
			for (int j = 0; j < queryGraph.adjacencyMatrix[i].size(); j++) {
				QueryEdge refineEdge = queryGraph.adjacencyMatrix[i].get(j);
				queryTargetIdRefine(i, refineEdge);
			}
		}
	}

	private void queryTargetIdRefine(int queryNodeId, QueryEdge refineEdge) {
		for (int k = 0; k < queryGraph.searchSpace.get(queryNodeId).size(); k++) {
			int candNodeId = queryGraph.searchSpace.get(queryNodeId).get(k);
			if (!nodeTest(candNodeId, refineEdge)) {
				queryGraph.searchSpace.get(queryNodeId).remove(k);
				k--;
			}
		}
	}

	private boolean nodeTest(int candNodeId, QueryEdge refineEdge) {
		if (dataGraph.adjacencyMatrix[candNodeId] == null) {
			return false;
		}
		for (int l = 0; l < dataGraph.adjacencyMatrix[candNodeId].size(); l++) {
			Edge targetEdge = dataGraph.adjacencyMatrix[candNodeId].get(l);
			if (queryGraph.searchSpace.get(refineEdge.getTargetId()).contains(
					targetEdge.getTargetId())) {
				if (targetEdge.satisfy(refineEdge)) {
					return true;
				}
			}
		}
		return false;
	}

	/*
	 * check.
	 */
	private boolean check(int qNodeId, int nodeId) {
		// if the candidate node already in the rlt
		// System.out.println(qNodeId + " "+nodeId);
		QueryAdjacencyList qedges = queryGraph.adjacencyMatrix[qNodeId];
		QueryAdjacencyList qedges2 = queryGraph.reverseAdjacencyMatrix[qNodeId];
		AdjacencyList dedges = dataGraph.adjacencyMatrix[nodeId];
		AdjacencyList dedges2 = dataGraph.reverseAdjacencyMatrix[nodeId];
		ArrayList<Edge> candEdges = new ArrayList<Edge>();
		if (qedges != null) {
			for (int i = 0; i < qedges.size(); i++) {
				if (qedges.get(i).getTargetId() > qNodeId) {
					break;
				}
				if (dedges == null) {
					return false;
				}
				int targetId = rltG.nodes.get(qedges.get(i).getTargetId())
						.getId();
				Edge e = dedges.edgeCheck(targetId, qedges.get(i));
				if (e == null) {
					Node node = rltG.nodes.remove(rltG.nodes.size() - 1);
					rltG.removeEdges(node);
					return false;
				} else {
					candEdges.add(e);
				}
			}
		}
		if (qedges2 != null) {
			for (int j = 0; j < qedges2.size(); j++) {
				if (qedges2.get(j).getSourceId() > qNodeId) {
					break;
				}
				int tmpId = qedges2.get(j).getSourceId();
				int sourceId = rltG.nodes.get(tmpId).getId();
				if (dedges2 == null) {
					return false;
				}
				Edge e = dedges2.edgeCheck2(sourceId, qedges2.get(j));
				if (e == null) {
					Node node = rltG.nodes.remove(rltG.nodes.size() - 1);
					rltG.removeEdges(node);
					return false;
				} else {
					candEdges.add(e);
				}
			}
		}
		rltG.addAllEdges(candEdges);
		return true;
	}

	private boolean isIn(int nodeId) {
		for (int i = 0; i < rltG.nodes.size(); i++) {
			if (nodeId == rltG.nodes.get(i).getId()) {
				return true;
			}
		}
		return false;
	}
}
